1. Field of the Invention
This invention relates to a method and apparatus for rendering trimmed parametric surfaces, especially trimmed NURBS surfaces, in a graphics system such as one in a high-performance graphics workstation.
2. Description of the Related Art
Graphics entities (also known as primitive elements, or primitives) consist of lines, curves, polygons, curved surfaces, and other two-dimensional (2D) and three-dimensional (3D) entities. These entities are usually stored in a form which efficiently encodes the basic parameters (endpoints of a line, center and radius of a circle, etc.), but is not directly representable on a raster-scan display, in which successive pixels, or pels, are illuminated as appropriate for the entity being represented. To "render" a graphics entity is to convert the entity from its high-level form ultimately to pixel data, which is stored in a frame buffer having a location for each pixel being displayed.
As disclosed in U.S. Pat. No. 5,278,948, one type of graphic entity, referred to as a NURBS (Non-Uniform Rational B-Spline) surface, is a particularly defined mapping from a 2D parametric coordinate space (U,V) to a 3D geometric coordinate space (X,Y,Z) in which the entity is actually viewed. An example of such a mapping might be a sphere, with U representing latitude and V representing longitude. More typically, however, NURBS representations would be used for surfaces (such as the wings or fuselage on an aircraft) that cannot be resolved into spherical, cylindrical or planar surfaces.
As described in the above-identified copending application, to facilitate the rendering process, the UV parameter space is divided, or tessellated, into contiguous U and V strips, or intervals, with the intervals intersecting to form a 2D array of UV rectangles. The NURBS surface is evaluated at the vertices of the UV rectangles by determining, for each vertex, the X, Y and Z geometric coordinates as well as the X, Y and Z components of a normal vector to the NURBS surface at that point. The vertex data for each UV rectangle is then set to a polygon processor, which processes the vertex data in a conventional manner to render the polygon. Thus, the polygon processor may generate edges of a defined color, fill the interior of the polygon with a predefined color, which may be different from the edge color, or shade the interior of the polygon, using the normal vector data to determining shading.
The NURBS surfaces described in the above-identified application are untrimmed surfaces, i.e. surfaces whose extents are defined simply by minimum and maximum values of the parametric coordinates U and V. It would be desirable also to be able to render trimmed NURBS surfaces, i.e. surfaces whose extent in the UV parametric coordinate space is defined by a trimming curve in that space.
A known method of rendering trimmed NURBS surfaces, which may be used in conjunction with the method described in the above-identified copending application, is to convert the trimming curve to a trim polyline (more particularly, a trim polygon enclosing a trimming region) approximating the trimming curve in parametric coordinate space. The trimming region bound by this trim polyline is made up of complete UV rectangles together with polygons of irregular shape formed by the intersection of the trimming region, bound by the trim polyline, with the UV rectangles along the periphery of the trimming region. The complete UV rectangles are rendered by the polygon processor in the usual manner. The irregular polygons, on the other hand, are recursively subdivided into rectangles which, in the aggregate, approximate the original irregular polygon. These smaller rectangles, whose dimensions in XYZ geometric coordinate space approximate those of a pixel, are then sent to the polygon processor.
While this method is capable of rendering trimmed NURBS surfaces, it would be desirable to have a method that does not necessitate the generation of numerous tiny polygons. Not only is the generation of such polygons a time-consuming act in itself, but the polygons generated also burden the polygon processor further down the graphics pipeline.